/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/trapping-rain-water
   @Language: C++
   @Datetime: 16-02-09 08:41
   */

class Solution {
public:
	/**
	 * @param heights: a vector of integers
	 * @return: a integer
	 */
	int trapRainWater(vector<int> &heights) {
		// write your code here
		int total=0,lm=0,l=0,rm=0,r=heights.size()-1;

		while(l<r){
			lm = max(lm,heights[l]);
			rm = max(rm,heights[r]);
			if (lm<rm) total += lm-heights[l++];
			else total += rm-heights[r--];
		}
		return total;
	}
};
